МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ДОСЛІДЖЕННЯ КОДОУТВОРЕННЯ ТА ПРИНЦИПІВ ПОБУДОВИ
КОДЕРІВ І ДЕКОДЕРІВ ЦИКЛІЧНИХ КОДІВ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 2
з курсу “Основи збору, передачі та обробки інформації”
для студентів базового напряму 6.1601
“Інформаційна безпека”
Затверджено
на засiданнi кафедри
"Захист інформації"
Протокол № 21 вiд 14. 06. 2007 p.
Львів 2007
Дослідження кодоутворення та принципів побудови кодерів і декодерів циклічних кодів: методичні вказівки до лабораторної роботи № 2 з курсу «Основи збору, передачі та обробки інформації» для студентів базового напрямку «Інформаційна безпека» усіх форм навчання / Укл. М. В. Кіріанакі, В. В. Хома, Я. Р. Совин. - Львів: НУЛП, 2007. - 9 с.
Укладачі: М. В. Кіріанакі, канд. техн. наук, доц., В. В. Хома, док. техн. наук, проф., Я. Р. Совин, канд. техн. наук, асист.
Відповідальний за випуск В. В. Хома, док. техн. наук, проф.
Рецензенти: А. Е. Лагун, канд. техн. наук, доц., З. М. Стрілецький, канд. техн. наук, доц.
Мета роботи – ознайомлення з основами кодування і декодування цифрової інформації циклічними кодами і набуттю практичних навиків розробки функціональних схем кодерів і декодерів.
1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Циклічні коди (ЦК) є одними з найпростіших в реалізації та ефективних у забезпеченні високої завадостійкості і завдяки цьому широко використовуються не лише в телемеханіці, але і в обчислювальній техніці та зв’язку.
Для утворення циклічних кодів використовуються так звані неприведені поліноми Р(х), тобто многочлени, які не можна представити добутком поліномів нижчих степенів. Існує декілька різних способів кодування [1, 2].
Найпростіший спосіб утворення ЦК полягає у множенні многочлена G(х)1, який відповідає інформаційним ni розрядам первинного (безнадлишкового) коду, на утворюючий поліном Р(х). Такий спосіб легко реалізувати, але йому притаманний суттєвий недолік: одержані в результаті множення комбінації ЦК не містять в явному вигляд інформаційні розряди. Після виправлення помилок такі комбінації для виділення інформаційних символів доводиться ділити на утворюючий поліном.
Інший спосіб передбачає відведення під інформаційні ni , символи старших розрядів коду, а під контрольні nk = n - ni, символів молодших розрядів. Для утворення ЦК використовується така процедура. Многочлен G(х) який відповідає ni - розрядній кодовій комбінації (КК) первинного коду, множиться на . Ця операція еквівалентна приписуванню із боку молодших розрядів G(х) - nk нулів. Добуток G(х)* ділиться на утворюючий поліном Р(х). При цьому одержують частку Q(x) того ж степеня, що і G(х), та залишок R(x), який додається до G(х)* . Отже, КК циклічного коду буде визначатися як поліном
F(x) = G(х)* ( R(х) (1)
Оскільки степінь Р(х) вибирають nk, степінь залишку R(х), не перевищує nk - 1. В комбінації, що відповідає многочленові G(х)* , nk молодших розрядів нульові, і відповідно, операція додавання (1) рівносильна приписуванню R(x) до G(x) з боку молодших розряд. Очевидно, що R(х) має зміст контрольних розрядів ЦК. Таким чином, циклічний код можна будувати, приписуючи до кожної комбінації безнадлишкового коду G(х) залишок від ділення G(х)* на утворюючий поліном Р(х) коду.
Захисні можливості ЦК визначаються утворюючим поліномом Р(х), вибір якого має бути підпорядкований кільком правилам:
1. кількість ненульових членів Р(х) має бути не меншою від кодової віддалі d;
2.степінь полінома Р(х) не може бути меншим за nk (бажано, щоб він дорівнював nk);
3. довжина Р(х) має бути мінімальною.
ЦК, утворений поліномом P(x)=x + 1, забезпечує кодову віддаль d = 2 і збігається з кодом з захистом за паритетом, забезпечуючи виявлення не лише поодиноких помилок, але і довільної непарної кількості помилок.
ЦК з d = 3 можуть виявляти поодинокі та подвійні помилки або виправляти по...